package Aula19;

import java.util.ArrayList;
import java.util.Iterator;

public class Splay {

	Arvore arvore;
	private String preOrdem;
	public static final String ZIG_DIR = "zigDIR";
	public static final String ZIG_ESQ = "zigESQ";
	public static final String ZIG_ZIG_DIR = "zig-zigDIR";
	public static final String ZIG_ZIG_ESQ = "zig-zigESQ";
	public static final String ZIG_ZAG_DIR = "zig-zagDIR";
	public static final String ZIG_ZAG_ESQ = "zig-zagESQ";

	public Splay() {
		arvore = new Arvore();
	}

	private ArrayList<RotacaoTupla> rotacionar(No no) {
		ArrayList<RotacaoTupla> rotacoes = new ArrayList<RotacaoTupla>();
		while (no.parent != null) {
			No parent = no.parent;
			if (parent.parent != null) {
				// Dupla
				No vo = parent.parent;
				if (parent.right == no && vo.right == parent) {
					// LEFT

					zigZigLeft(no);
					String pai = null;
					if (no.parent != null) {
						pai = no.parent.key + "";
					}
					rotacoes.add(new RotacaoTupla(ZIG_ZIG_ESQ, pai));

				} else if (parent.left == no && parent.parent.left == parent) {
					// RIGHT

					zigZigRight(no);
					String pai = null;
					if (no.parent != null) {
						pai = no.parent.key + "";
					}
					rotacoes.add(new RotacaoTupla(ZIG_ZIG_DIR, pai));

				} else {
					// ZIG ZAG
					if (parent.right == no) {
						// LEFT

						zigZagLeft(no);
						String pai = null;
						if (no.parent != null) {
							pai = no.parent.key + "";
						}
						rotacoes.add(new RotacaoTupla(ZIG_ZAG_ESQ, pai));

					} else {
						// RIGHT

						zigZagRight(no);
						String pai = null;
						if (no.parent != null) {
							pai = no.parent.key + "";
						}
						rotacoes.add(new RotacaoTupla(ZIG_ZAG_DIR, pai));
					}
				}
			} else {
				// SIMPLES
				if (parent.right == no) {
					// LEFT

					zigLeft(no);
					String pai = null;
					if (no.parent != null) {
						pai = no.parent.key + "";
					}
					rotacoes.add(new RotacaoTupla(ZIG_ESQ, pai));

				} else {
					// RIGHT

					zigRight(no);
					String pai = null;
					if (no.parent != null) {
						pai = no.parent.key + "";
					}
					rotacoes.add(new RotacaoTupla(ZIG_DIR, pai));
				}
			}
			if(no.parent != null){
				if(no.parent.key > no.key){
					no.parent.left = no;
				}else{
					no.parent.right = no;
				}
			}
		}
		arvore.raiz = no;
		return rotacoes;
	}

	private void zigRight(No no) {

		No parent = no.parent;
		No t2 = no.right;
		No t3 = parent.right;
		no.parent = parent.parent;
		no.right = parent;
		parent.parent = no;
		parent.left = t2;
		if (t2 != null)
			t2.parent = parent;
		parent.right = t3;
		if (t3 != null)
			t3.parent = parent;

	}

	private void zigLeft(No no) {
		No parent = no.parent;
		No t2 = no.left;
		No t3 = no.right;
		no.parent = parent.parent;
		no.left = parent;
		no.right = t3;
		if (t3 != null)
			t3.parent = no;
		parent.parent = no;
		parent.right = t2;
		if (t2 != null)
			t2.parent = parent;
	}

	private void zigZigRight(No no) {
		No parent = no.parent;
		No vo = parent.parent;
		No t2 = no.right;
		No t3 = parent.right;
		No t4 = vo.right;
		no.parent = vo.parent;
		no.right = parent;
		parent.parent = no;
		parent.left = t2;
		if (t2 != null)
			t2.parent = parent;
		parent.right = vo;
		vo.parent = parent;
		vo.left = t3;
		if (t3 != null)
			t3.parent = vo;
		vo.right = t4;
		if (t4 != null)
			t4.parent = vo;
	}

	private void zigZigLeft(No no) {
		No parent = no.parent;
		No vo = parent.parent;
		No t2 = parent.left;
		No t3 = no.left;
		No t4 = no.right;
		no.parent = vo.parent;
		no.left = parent;
		no.right = t4;
		if (t4 != null)
			t4.parent = no;
		parent.parent = no;
		parent.left = vo;
		parent.right = t3;
		if (t3 != null)
			t3.parent = parent;
		vo.parent = parent;
		vo.right = t2;
		if (t2 != null)
			t2.parent = vo;
	}

	private void zigZagLeft(No no) {
		No parent = no.parent;
		No vo = parent.parent;
		No t2 = no.left;
		No t3 = no.right;
		No t4 = vo.right;
		parent.parent = no;
		parent.right = t2;
		if (t2 != null)
			t2.parent = parent;
		no.parent = vo.parent;
		no.left = parent;
		no.right = vo;
		vo.parent = no;
		vo.left = t3;
		if (t3 != null)
			t3.parent = vo;
		vo.right = t4;
		if (t4 != null)
			t4.parent = vo;
	}

	private void zigZagRight(No no) {
		No parent = no.parent;
		No vo = parent.parent;
		No t2 = no.left;
		No t3 = no.right;
		No t4 = parent.right;
		parent.parent = no;
		parent.left = t3;
		if (t3 != null)
			t3.parent = parent;
		parent.right = t4;
		if (t4 != null)
			t4.parent = parent;
		no.parent = vo.parent;
		no.left = vo;
		no.right = parent;
		vo.parent = no;
		vo.right = t2;
		if (t2 != null)
			t2.parent = vo;
	}

	private String rotacoesStr(No no) {
		String saida = null;
		if (no != null) {
			saida = "";
			Iterator<RotacaoTupla> iterator = rotacionar(no).iterator();
			for (; iterator.hasNext();) {
				saida += iterator.next();
				if (iterator.hasNext()) {
					saida += ", ";
				}
			}
		}
		return saida;
	}

	private void preOrdem(No n) {

		if (n != null) {
			preOrdem += n.key;
			if (n.left != null) {
				preOrdem += " ";
			}
			preOrdem(n.left);
			if (n.right != null) {
				preOrdem += " ";
			}
			preOrdem(n.right);
		}
	}

	public String preOrdemStr() {
		preOrdem = "";
		preOrdem(arvore.raiz);
		return preOrdem;
	}

	public String inserir(int n) {
		No no = arvore.insert(n);
		return rotacoesStr(no);
	}

	public String search(int n) {
		No no = arvore.search(n);
		return rotacoesStr(no);
	}
}
